import com.sun.corba.se.impl.oa.poa.ActiveObjectMap;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
 }


class CBTInserter {
    TreeNode root;
    Queue<TreeNode> queue=new ArrayDeque<>();
    public CBTInserter(TreeNode root) {
        this.root=root;
        Queue<TreeNode> q=new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()){
            TreeNode node=q.poll();
            if(node.left==null||node.right==null){
                queue.add(node);
            }
            if(node.left!=null){
                q.add(node.left);
            }
            if(node.right!=null){
                q.add(root.right);
            }
        }
    }

    public int insert(int val) {
        TreeNode node=queue.peek();
        if(node.left==null){
            node.left=new TreeNode(val);
            queue.add(node.left);
        }else{
            node.right=new TreeNode(val);
            queue.poll();
            queue.add(node.right);
        }
        return node.val;
    }

    public TreeNode get_root() {
        return root;
    }
}










class CBTInserter1 {
    TreeNode root;
    Queue<TreeNode> queue1=new ArrayDeque<>();
    public CBTInserter1(TreeNode root) {
        this.root=root;
        Queue<TreeNode> queue2=new ArrayDeque<>();
        queue2.offer(root);
        while (!queue2.isEmpty()){
            TreeNode cur=queue2.poll();
            if(cur.left==null||cur.right==null){
                queue1.add(cur);
            }
            if(cur.left!=null){
                queue2.add(cur.left);
            }
            if(cur.right!=null){
                queue2.add(cur.right);
            }
        }
    }

    public int insert(int v) {
        TreeNode cur=queue1.peek();
        if(cur.left==null){
            cur.left=new TreeNode(v);
            queue1.add(cur.left);
        }else{
            cur.right=new TreeNode(v);
            queue1.add(cur.right);
            queue1.poll();
        }
        return cur.val;
    }

    public TreeNode get_root() {
        return root;
    }
}
public class project {
    public int myAtoi(String s) {
        int len=s.length();
        char[] str=s.toCharArray();
        int index=0;
        while (index<len&&str[index]==' '){
            index++;
        }
        if(index==len){
            return 0;
        }
        int i=1;
        if(str[index]=='+'){
            index++;
        }else if(str[index]=='-'){
            index++;
            i=-1;
        }
        int ret=0;
        while (index<len){
            char ch=str[index];
            if(ch<'0'||ch>'9'){
                break;
            }
            if(ret>Integer.MAX_VALUE/10||(ret==Integer.MAX_VALUE/10&&ch-'0'>Integer.MAX_VALUE%10)){
                return Integer.MAX_VALUE;
            }
            if(ret<Integer.MIN_VALUE/10||(ret==Integer.MIN_VALUE/10&&ch-'0'>-(Integer.MIN_VALUE%10))){
                return Integer.MIN_VALUE;
            }
            ret=ret*10+i*(ch-'0');
            index++;
        }
        return ret;
    }














    public int strToInt(String str) {
        int len=str.length();
        char[] s=str.toCharArray();
        int index=0;
        while (index<len&&s[index]==' '){
            index++;
        }
        if(index==len){
            return 0;
        }
        int i=1;
        if(s[index]=='+'){
            index++;
        }else if(s[index]=='-'){
            i=-1;
            index++;
        }
        int ret=0;
        while (index<len){
            char ch=s[index];
            if(ch<'0'||ch>'9'){
                break;
            }
            if(ret>Integer.MAX_VALUE/10||(ret==Integer.MAX_VALUE/10&&(ch-'0')>Integer.MAX_VALUE%10)){
                return Integer.MAX_VALUE;
            }
            if(ret<Integer.MIN_VALUE/10||(ret==Integer.MIN_VALUE/10&&(ch-'0')>-(Integer.MIN_VALUE%10))){
                return Integer.MIN_VALUE;
            }
            ret=ret*10+i*(ch-'0');
            index++;
        }
        return ret;
    }
















    public String minNumber(int[] nums) {
        String[] str=new String[nums.length];
        for(int i=0;i<nums.length;i++){
            str[i]=String.valueOf(nums[i]);
        }
        Arrays.sort(str, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o1+o2).compareTo(o2+o1);
            }
        });
        StringBuilder sb=new StringBuilder();
        for(String s : str){
            sb.append(s);
        }
        return sb.toString();
    }














    public int findJudge(int n, int[][] trust) {
        int[] arr=new int[n+1];
        for(int[] tmp : trust){
            arr[tmp[0]]--;
            arr[tmp[1]]++;
        }
        for(int i=1;i<=n;i++){
            if(arr[i]==n-1){
                return i;
            }
        }
        return -1;
    }
}
